//
// Created by 周智超 on 2020/6/15.
//

#ifndef STRUCTURE_STRING_H
#define STRUCTURE_STRING_H
#include "normal.h"
#include <iostream>




void nextV1(char *str, int next[])
{
   int j = 1;
   next[1] = 0;
   int t = 0;
   while (str[j] != '\0')
   {
       if(t == 0 || str[t] == str[j])
       {
           next[j+1] = t + 1;
           j++;
           t++;
           std::cout << j << "  " << t << std::endl;
       } else {
           t = next[t];
       }
   }
}

void nextValV1(char * str, int nextval[])
{
    int j = 1;
    nextval[1] = 0;
    int t = 0;
    while (str[j] != '\0')
    {
        if(t == 0 || str[j] == str[t])
        {
            if(str[j+1] != str[t+1])
            {
                nextval[j+1] = t + 1;
            }
            else
            {
                nextval[j+1] = nextval[t+1];
            }
            j++;
            t++;
            std::cout << j << "  " << nextval[j] << std::endl;

        }
        else
        {
            t = nextval[t];
        }
    }
}
int kmpPos(char *origin, char *substr, int next[], int pos);
int showTimes(char *origin, char *substr, int next[])
{
    int times = 0;
    int pos = 1;
    int findLocation;
    int subLen = strlen(substr)-1;
    int len = strlen(origin);
    while (pos < len)
    {
        findLocation = kmpPos(origin, substr, next, pos);
        if(findLocation == -1)
        {
            return times;
        }
        times++;
        pos = findLocation + subLen;
    }
    return times;
}

int kmpPos(char *origin, char *substr, int next[], int pos)
{
    int i = pos;
    int j = 1;
    while (origin[i] != '\0' && substr[j] != '\0')
    {
        if(j == 0 || origin[i] == substr[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }
    if(j > strlen(substr) -1)
    {
        return i - strlen(substr) + 1;
    }
    return -1;

}
int kmp(char *origin, char *substr, int next[])
{
    int i = 1;
    int j = 1;
    while (origin[i] != '\0' && substr[j] != '\0')
    {
        if(j == 0 || origin[i] == substr[j]) // j=0代表没有公共前缀，则origin往后移一位从下个比较
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }
    if(j > strlen(substr) - 1)
        return i - (strlen(substr)-1);
    return 0;
}


void replace(char *origin, char src, char dest)
{
    int i = 0;
    for(;origin[i] != '\0'; i++)
    {
        if(origin[i] == src)
            origin[i] = dest;
    }
}

void reverse(char *origin)
{
    int i = 0;
    int j = 0;
    char temp;
    while(origin[j] != '\0')
    {
        j++;
    }
    if(j == i)
    {
        return ;
    }
    j--;
    for(;i < j; i++,j--)
    {
        temp = origin[i];
        origin[i] = origin[j];
        origin[j] = temp;
    }
}

void removeElement(char *s, char target)
{
    int newLength = 0;
    int i = 0;
    for(; s[i] != '\0';i++)
    {
        if(s[i] != target)
        {
            s[newLength] = s[i];
            newLength++;
        }
    }
    s[newLength] = '\0';
}

typedef  struct Str {
    char data[maxSize+1];
    int length;
} Str;

int initStr(Str *&s, char origin[])
{
    int ol ;
    ol = strlen(origin);
    s = (Str *)malloc(sizeof(Str));
    if(s == NULL)
    {
        return 0;
    }
    s->length = ol;
    for(int i = 0; i < s->length;i++)
    {
        s->data[i] = origin[i];
    }
    s->data[s->length] = '\0';
    return 1;
}

void del(Str *&s, int begin, int end)
{
    int i = begin;
    if(end >= s->length)
    {
        end = s->length - 1;
    }
    int j = end + 1;
    for(; j < s->length; i++,j++)
    {
        s->data[i] = s->data[j];
    }
    s->length = s->length - (end - begin + 1);
    s->data[s->length] = '\0';
}

void insert(Str *&s1, Str *&s2, int begin, int end)
{
    int subLength = end - begin + 1;
    int diff = s2->length - subLength;
    int i , j;
    if(diff > 0)
    {
        i = s1->length + diff - 1;
        j = s1->length - 1;
        for(; j > end; i--,j--)
        {
            s1->data[i] = s1->data[j];
        }
    }
    else
    {
        i = begin + s2->length;
        j = end + 1;
        for(; j < s1->length; j++,i++)
        {
            s1->data[i] = s1->data[j];
        }
    }
    i = 0;
    j = begin;
    for(; i < s2->length;i++,j++)
    {
        s1->data[j] = s2->data[i];
    }
    s1->length = s1->length + diff;
    s1->data[s1->length] = '\0';
}

#endif //STRUCTURE_STRING_H
